package com.lw.leetcode.hash.b;


import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 面试题 16.25. LRU 缓存
 * 146. LRU 缓存机制
 * 剑指 Offer II 031. 最近最少使用缓存
 *
 * @author liw
 */
public class LRUCache {

    public static void main(String[] args) {
        LRUCache test = new LRUCache(2);
        test.put(1, 1);
        test.put(2, 2);
        int i = test.get(1);
        System.out.println(i);
        test.put(3, 3);
        i = test.get(2);
        System.out.println(i);
        test.put(4, 4);
        i = test.get(1);
        System.out.println(i);
        i = test.get(3);
        System.out.println(i);
        i = test.get(4);
        System.out.println(i);
    }

    private int capacity;
    private int count;
    private Node st;
    private Node end;
    private Map<Integer, Node> nodeMap;

    public LRUCache(int n) {
        this.capacity = n;
        this.nodeMap = new HashMap<>();
        this.st = new Node(0, 0);
        this.end = new Node(0, 0);
        end.prev = st;
        st.next = end;
    }

    public void put(int key, int value) {
        Node node = nodeMap.get(key);
        if (node == null) {
            node = new Node(key, value);
            if (count < capacity) {
                count++;
            } else {
                nodeMap.remove(st.next.key);
                removeNode(st.next);
            }
            putLast(node);
        } else {
            node.val = value;
            removeNode(node);
            putLast(node);
        }
        nodeMap.put(key, node);
    }

    public int get(int key) {
        Node node = nodeMap.get(key);
        if (node == null) {
            return -1;
        }
        removeNode(node);
        putLast(node);
        return node.val;
    }

    private void putLast(Node node) {
        Node prev = end.prev;
        prev.next = node;
        node.prev = prev;
        node.next = end;
        end.prev = node;
    }

    private void removeNode(Node node) {
        Node prev = node.prev;
        prev.next = node.next;
        node.next.prev = prev;
    }

    private static class Node {
        public int key;
        public int val;
        public Node prev;
        public Node next;

        public Node(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }

}


